package SortAlgorithm;

/**
 * @author zxc
 * @date 2023/01/15 20:41
 **/

import LinkedList.ListNode;

import java.util.PriorityQueue;

/**
 *  题目 ：合并排序链表
 *  题目详述 ：
 *  给定一个链表数组，每个链表都已经按升序排列。
 *  请将所有链表合并到一个升序链表中，返回合并后的链表。
 */
public class MergeKLists_MinHeap {
    /**
     * 思路 ：最小堆，来实现k个排序链表合并为一个排序链表；
     * （1）首先，k个指针分别指向k个排序链表的头节点，
     * （2）同时,将指针所指向的节点加入到最小堆中；（即，最小堆中堆顶元素就是当前k个指针所指向链表节点中最小值）
     * （3）直到最小堆中为空，即说明了k个排序链表已经被合并为一个升序链表；
     */
    public ListNode mergeKLists(ListNode[] lists) {
        // 合并后链表的虚拟头结点
        ListNode dummy = new ListNode(0);
        ListNode node = dummy;
        // 创建并且初始化最小堆，同时定义比较规则（即，实现Comparable接口）
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>(
                (p1 , p2) -> p1.val - p2.val
        );
        // lists链表数组中所存储的所需要合并链表，都是升序链表；
        // 即，k个指针分别指向k个链表的头结点即可；
        for (ListNode list : lists) {
            if(list != null){
                minHeap.offer(list);
            }
        }
        // while循环结束条件 : 即，最小堆minHeap为空，代表了k个合并链表中所有链表节点都已经被遍历，同时已经被加入到合并后的链表中；
        while(!minHeap.isEmpty()){
            // 将minHeap最小堆中堆顶元素移出（其代表了当前k个指针所指向链表节点中的最小值）
            ListNode pollNode = minHeap.poll();
            // 将刚刚移除的pollNode链表节点，接到合并后的链表中；
            node.next = pollNode;
            // node节点后移（即，保证node节点始终指向合并后链表的尾节点）
            node = node.next;
            // 若是pollNode节点的next节点不为null的话，即需要将next节点加入到最小堆中；
            if(pollNode.next != null){
                minHeap.offer(pollNode.next);
            }
        }
        // 返回合并合并后链表的虚拟头结点的next节点；
        return dummy.next;
    }
    /**
     * 分析 ：
     * （1）空间复杂度 ：O（k）（k，为排序链表总数）
     * （2）时间复杂度 ：O（nlogk）
     * （由于堆中的插入，查找和删除操作的时间复杂度皆为O（logk），同时需要去遍历list链表数组中所有的链表节点，对其进行排序；）
     *  ===》 总的时间复杂度 ：O（nlogk）（n，为链表数组中所有链表节点数目）
     */
}
